﻿#pragma once
#include "Index.h"

class IUniqueBinarySearchTreeCombineCount
{
public:
	/**
	 * 有多少个不同的二叉搜索树.
	 * https://www.nowcoder.com/practice/16d23f940a084023b3be6019262589dc?tpId=230&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D230
	 *
	 * 描述
	 * 给定一个由节点值从 1 到 n 的 n 个节点。请问由多少种不同的方法用这 n 个节点构成互不相同的二叉搜索树。
	 *
	 * 数据范围：1≤n≤19 
	 * 输入描述：仅一行输入一个正整数 n ，表示节点的数量。
	 * 输出描述：输出组成不同二叉搜索树的方法数。
	 */
	virtual int getUniqueBinarySearchTreeCombineCount(int nNodes) = 0;
};

class UniqueBinarySearchTreeCombineCount
{
public:
	class Recursive:public IUniqueBinarySearchTreeCombineCount
	{
	public:
		int getUniqueBinarySearchTreeCombineCount(int nNodes) override
		{
			if (nNodes <= 0)
				return 0;
			if (nNodes == 1 || nNodes == 2)
				return nNodes;
			if (_combineCounts.count(nNodes))
				return _combineCounts[nNodes];

			int combineCount = 0;
			for (int root = 1; root <= nNodes; ++root)
			{
				const int leftChildrenCount = root - 1;
				const int rightChildrenCount = nNodes - root;

				const int leftCombines = leftChildrenCount > 0 ?
					getUniqueBinarySearchTreeCombineCount(leftChildrenCount) : 1;
				const int rightCombines = rightChildrenCount > 0 ?
					getUniqueBinarySearchTreeCombineCount(rightChildrenCount) : 1;

				combineCount += leftCombines * rightCombines;
			}
			_combineCounts[nNodes] = combineCount;
			return combineCount;
		}
	private:
		std::unordered_map<int, int> _combineCounts;
	};
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
class UniqueBinarySearchTreeCombineCountTest :public SolutionTestor<IUniqueBinarySearchTreeCombineCount>
{
protected:
	void LoadSolutions(std::vector<IUniqueBinarySearchTreeCombineCount*>& solutions) override
	{
		solutions = {
			new UniqueBinarySearchTreeCombineCount::Recursive,
		};
	}
};
TEST_F(UniqueBinarySearchTreeCombineCountTest, getUniqueBinarySearchTreeCombineCount)
{
	const std::vector<int> answers = { 1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,
		2674440,9694845,35357670,129644790,477638700,1767263190};

	TestForSolutions([&answers](IUniqueBinarySearchTreeCombineCount* solution)
		{
			for (int i = 1; i <= answers.size(); ++i)
			{
				const auto result = solution->getUniqueBinarySearchTreeCombineCount(i);
				const auto expectResult = answers[i - 1];
				EXPECT_EQ(result, expectResult);
			}
		});
}
#endif
